package 动态规划;

public class LeetCode72_编辑距离 {
    //典型的动态规划
    public int minDistance(String word1, String word2) {
        if(word1 == null) {
            return word2.length();
        }
        if(word2 == null) {
            return word1.length();
        }
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] minDis = new int[len1+1][len2+1];
        // 因为有三次操作，从每一个子过程中找次数最少的那个过程，

        // F(i,j)初始化
        for(int i = 0; i <= len1; ++i) {
            minDis[i][0] = i;
        }
        for(int j = 0; j <= len2; ++j) {
            minDis[0][j] = j;
        }
        for(int i = 1; i <= len1; ++i) {
            for(int j = 1; j <= len2; ++j) {
                minDis[i][j] = 1 + Math.min(minDis[i-1][j], minDis[i][j-1]);

                //判断word1的第i个字符是否与word2的第j个字符相等
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    // 字符相等，F(i-1, j-1)编辑距离不变
                    minDis[i][j] = Math.min(minDis[i][j], minDis[i-1][j-1]);
                }else {
                    // 字符不想等，F(i-1, j-1)编辑距离 + 1
                    minDis[i][j] = Math.min(minDis[i][j], minDis[i-1][j-1] + 1);
                }
            }
        }
        return minDis[len1][len2];
    }
}
